<!DOCTYPE html>
<html>
<head hexo-theme='https://volantis.js.org/#3.0-beta1'>
  <meta charset="utf-8">
  <!-- SEO相关 -->
  
    
  
  <!-- 渲染优化 -->
  <meta name="renderer" content="webkit">
  <meta name="force-rendering" content="webkit">
  <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
  <meta name="HandheldFriendly" content="True" >
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

  <!-- 页面元数据 -->
  
  <title>splay - Zlii</title>
  

  
    <meta name="description" content="介绍平衡树的一种—Splay">
  

  <!-- feed -->
  

  <!-- import meta -->
  

  <!-- link -->
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.13/css/all.min.css">
  
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">


  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.css">

  

  

  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer@1.10/dist/APlayer.min.css">
  

  

  <!-- import link -->
  

  
  
    
<link rel="stylesheet" href="/css/style.css">

  

  
  
</head>

<body>
  
  
  
  <div class="cover-wrapper">
    <cover class='cover post' style="display: none;">
      <div class='cover-body'>
  <div class='a'>
    
    
      <p class="title">Zlii</p>
    
    
  </div>
  <div class='b'>
    
      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <input type="text" class="input u-search-input" placeholder="搜索..." />
          <i class="icon fas fa-search fa-fw"></i>
        </form>
      </div>
    
    <div class='menu navigation'>
      <ul class='cover-list-h'>
        
          
            <li>
              <a class="nav home"
                href="/"
                
                
                id="home">
                <i class='fa fa-home fa-fw'></i>主页
              </a>
            </li>
          
            <li>
              <a class="nav home"
                href="/categories/"
                
                
                id="categories">
                <i class='fas fa-folder-open fa-fw'></i>分类
              </a>
            </li>
          
            <li>
              <a class="nav home"
                href="/tags/"
                
                
                id="tags">
                <i class='fas fa-tags fa-fw'></i>标签
              </a>
            </li>
          
            <li>
              <a class="nav home"
                href="/archives/"
                
                
                id="archives">
                <i class='fas fa-archive fa-fw'></i>归档
              </a>
            </li>
          
        
      </ul>
    </div>
  </div>
</div>

      <div class="scroll-down" style="display: none;"><i class="fa fa-chevron-down scroll-down-effects"></i></div>
    </cover>
    <header class="l_header shadow blur">
  <div class='container'>
  <div class='wrapper'>
    <div class='nav-sub'>
      <p class="title"></p>
      <ul class='switcher nav-list-h'>
        <li><a class="s-comment fas fa-comments fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
          <li><a class="s-toc fas fa-list fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
      </ul>
    </div>
		<div class="nav-main">
      
        
        <a class="title flat-box" target="_self" href='/'>
          
          
          
            Zlii
          
        </a>
      

			<div class='menu navigation'>
				<ul class='nav-list-h'>
          
          
          
            
            
              <li>
                <a class="flat-box" href=/
                  
                  
                  
                    id="home"
                  >
                  <i class='fa fa-home fa-fw'></i>主页
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="flat-box" href=/categories/
                  
                  
                  
                    id="categories"
                  >
                  <i class='fas fa-folder-open fa-fw'></i>分类
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="flat-box" href=/tags/
                  
                  
                  
                    id="tags"
                  >
                  <i class='fas fa-tags fa-fw'></i>标签
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="flat-box" href=/archives/
                  
                  
                  
                    id="archives"
                  >
                  <i class='fas fa-archive fa-fw'></i>归档
                </a>
                
              </li>
            
          
          
				</ul>
			</div>

      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <i class="icon fas fa-search fa-fw"></i>
          <input type="text" class="input u-search-input" placeholder="搜索..." />
        </form>
      </div>

			<ul class='switcher nav-list-h'>
				
					<li><a class="s-search fas fa-search fa-fw" target="_self" href='javascript:void(0)'></a></li>
				
				<li>
          <a class="s-menu fas fa-bars fa-fw" target="_self" href='javascript:void(0)'></a>
          <ul class="menu-phone list-v navigation white-box">
            
              
            
              <li>
                <a class="flat-box" href=/
                  
                  
                  
                    id="home"
                  >
                  <i class='fa fa-home fa-fw'></i>主页
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="flat-box" href=/categories/
                  
                  
                  
                    id="categories"
                  >
                  <i class='fas fa-folder-open fa-fw'></i>分类
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="flat-box" href=/tags/
                  
                  
                  
                    id="tags"
                  >
                  <i class='fas fa-tags fa-fw'></i>标签
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="flat-box" href=/archives/
                  
                  
                  
                    id="archives"
                  >
                  <i class='fas fa-archive fa-fw'></i>归档
                </a>
                
              </li>
            
          
            
          </ul>
        </li>
			</ul>
		</div>
	</div>
  </div>
</header>

  </div>
  

  <div class="l_body nocover">
    <div class='body-wrapper' id="pjax-container">
      
        <!--此文件用来存放一些不方便取值的变量-->
<!--思路大概是将值藏到重加载的区域内-->



<div id="pjax-data" style="display: none">
  <div id="pjax-ispage">true</div>
  <div id="pjax-pageTitle">splay</div>
  <div id="pjax-enable-cover">true</div>
  
  <div id="valine-path">none</div>
  <div id="valine-placeholder">none</div>
  
  
</div>


<script>
  // 处理封面 此时 jquery 还没加载
  if ("none" == "none") { // 移除封面
    document.getElementsByClassName('cover')[0].style.display = "none";
    document.getElementsByClassName('l_body')[0].classList.add("nocover");
    document.getElementsByClassName('l_header', 'cover-wrapper')[0].classList.add("show");
  } else {
    if ("none" == "blog") { // 半屏
      document.getElementsByClassName('cover')[0].classList.remove("full");
      document.getElementsByClassName('cover')[0].classList.add("half");
      document.getElementsByClassName('scroll-down')[0].style.display = "none";
    } else if ("none" == "docs") { // 全屏
      document.getElementsByClassName('cover')[0].classList.remove("half");
      document.getElementsByClassName('cover')[0].classList.add("full");
      document.getElementsByClassName('scroll-down')[0].style.display = "";
    }
    document.getElementsByClassName('cover')[0].style.display = "";
    document.getElementsByClassName('l_body', 'show')[0].classList.remove("nocover");
    document.getElementsByClassName('l_header', 'cover-wrapper')[0].classList.remove("show");
  }
</script>

      
      

<div class='l_main'>
  

  
    <article id="post" class="post white-box reveal shadow article-type-post" itemscope itemprop="blogPost">
      


  <section class='meta'>
    
      
      
      <div class="meta" id="header-meta">
        
          
  <h1 class="title">
    <a href="/2020/07/12/splay/">
      splay
    </a>
  </h1>


        
        <div class='new-meta-box'>
          
            
          
            
              
<div class='new-meta-item author'>
  <a href="/" rel="nofollow">
    <img no-lazy src="/img/head.jpg">
    <p>YouXam</p>
  </a>
</div>

            
          
            
              
  
  <div class='new-meta-item category'>
    <a href='/categories/%E7%AE%97%E6%B3%95/%E5%B9%B3%E8%A1%A1%E6%A0%91/' rel="nofollow">
      <i class="fas fa-folder-open fa-fw" aria-hidden="true"></i>
      <p>算法/平衡树</p>
    </a>
  </div>


            
          
            
              <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt fa-fw" aria-hidden="true"></i>
    <p>发布于：Jul 12, 2020</p>
  </a>
</div>

            
          
            
              

            
          
        </div>
        
          <hr>
        
      </div>
    
  </section>


      <section class="article typo">
        <div class="article-entry" itemprop="articleBody">
          
          
          <p>介绍平衡树的一种—Splay</p>
<a id="more"></a>
<h1 id="引入"><a href="#引入" class="headerlink" title="引入"></a>引入</h1><h2 id="BST-二叉排序树"><a href="#BST-二叉排序树" class="headerlink" title="BST(二叉排序树)"></a>BST(二叉排序树)</h2><p>一棵空树，或者是具有下列性质的二叉树：</p>
<ol>
<li>若左子树不空，则左子树上所有结点的值均小于它的根结点的值；</li>
<li>若右子树不空，则右子树上所有结点的值均大于它的根结点的值；</li>
<li>左、右子树也分别为二叉排序树；</li>
<li>没有键值相等的结点。</li>
</ol>
<p>但是当插入数据有序时， BST会退化为一条链， 时间复杂度就会变为O(n), 所以就有了平衡树</p>
<h2 id="平衡树"><a href="#平衡树" class="headerlink" title="平衡树"></a>平衡树</h2><p>在保证BST的性质不变的情况下， 将树结构进行变换， 使树结构接近完全平衡树， 使查询时间复杂度为O(\log n)。</p>
<h2 id="Splay-伸展树"><a href="#Splay-伸展树" class="headerlink" title="Splay(伸展树)"></a>Splay(伸展树)</h2><blockquote>
<p>假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。</p>
</blockquote>
<h1 id="基本操作"><a href="#基本操作" class="headerlink" title="基本操作"></a>基本操作</h1><h2 id="本文代码变量含义"><a href="#本文代码变量含义" class="headerlink" title="本文代码变量含义"></a>本文代码变量含义</h2><ol>
<li><code>ch[x][k]</code> : 编号为x的节点的子节点的编号。当k=0， 存储左子节点， 当k=1, 存储右子节点。</li>
<li><code>cnt[x]</code> : 相同的点的存在个数</li>
<li><code>size[x]</code> : 编号为x的子树的大小</li>
<li><code>v[x]</code> : 编号为x的节点的值</li>
<li><code>f[x]</code> : 编号为x的节点的父节点</li>
<li><code>root</code> : 树的根</li>
<li><code>tot</code> : 节点总数</li>
</ol>
<h2 id="更新"><a href="#更新" class="headerlink" title="更新"></a>更新</h2><p>每次树的结构变化， 都要维护一下<code>size</code></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123; size[x] = size[ch[x][<span class="number">0</span>]] + size[ch[x][<span class="number">1</span>]] + cnt[x]; &#125;</span><br></pre></td></tr></table></figure>
<p>x的子树大小为左右子节点的子树大小加其本身大小。</p>
<h2 id="单旋"><a href="#单旋" class="headerlink" title="单旋"></a>单旋</h2><p>将某个节点向上旋转， 使其深度减小， 同时保证BST的性质不被破坏。</p>
<p><img src="https://www.z4a.net/images/2018/11/23/Untitled-Diagram.png" alt=""></p>
<p><em>此图将x向上旋转</em></p>
<p>简单描述过程就是x旋转到y的位置， x的右子树变为y的左子树， y变为x的右子树， 其他不变。</p>
<p>当x为y的左子节点， 旋转操作如上图， 当x为y的右子节点， 旋转操作与上图对称。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">rotate</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> y = f[x], z = f[y], k = (ch[y][<span class="number">1</span>] == x); <span class="comment">// k为x相对于y的位置</span></span><br><span class="line">	ch[z][ch[z][<span class="number">1</span>] == y] = x, f[x] = z; <span class="comment">// x旋转到y的位置, 维护父亲</span></span><br><span class="line">	ch[y][k] = ch[x][!k], f[ch[x][!k]] = y; <span class="comment">// x的右子树变为y的左子树， 维护父亲</span></span><br><span class="line">	ch[x][!k] = y, f[y] = x; <span class="comment">// y变为x的右子树， 维护父亲</span></span><br><span class="line">	update(y), update(x); <span class="comment">// 先更新深度大的， 再更新深度小的</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="Splay-伸展"><a href="#Splay-伸展" class="headerlink" title="Splay(伸展)"></a>Splay(伸展)</h2><p>splay就是把某个节点向上旋转若干次， 使节点到达某个位置</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">splay</span> <span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> t)</span> </span>&#123; <span class="comment">//把x旋转到父亲为t的位置</span></span><br><span class="line">	<span class="keyword">while</span> (f[x] != t) &#123; <span class="comment">//x的父亲不为t就执行</span></span><br><span class="line">		<span class="keyword">int</span> y = f[x], z = f[y];</span><br><span class="line">		<span class="keyword">if</span> (z != t) (ch[y][<span class="number">0</span>] == x) == (ch[z][<span class="number">0</span>] == y) ? rotate(y) : rotate(x);  <span class="comment">// 如果z-y-x方向一样， 就旋转y, 否则旋转x</span></span><br><span class="line">		rotate(x); <span class="comment">// 然后再旋转x</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (!t) root = x; <span class="comment">// 如果旋转到了根节点， 更新根节点</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>为什么如果z-y-x方向一样(都向左偏或向右偏)， 就要旋转一下y呢？</p>
<p>自己画一下就会发现， 在这种情况下， 如果只旋转两次x， 有一条链结构没有变化， 而先旋转y再旋转x，就改变了所有链的结构和子树的深度。</p>
<p>这样更利于查询。</p>
<h2 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">find</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> u = root;</span><br><span class="line">	<span class="keyword">while</span> (ch[u][x &gt; v[u]] &amp;&amp; x != v[u]) u = ch[u][x &gt; v[u]]; <span class="comment">// 不断向下找</span></span><br><span class="line">	splay(u, <span class="number">0</span>); <span class="comment">// 最后要splay, 维护平衡</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>有两点要注意：</p>
<ol>
<li>这个查找操作保证查找时树不为空， 因为为了避免越界， 减少边界情况的判断， 通常会先插入一个正无穷和负无穷， 所以查找时不用特殊判断， 否则要特判树为空的情况。</li>
<li>当<code>x &gt; v[u]</code>, <code>x &gt; v[u]</code> 为 <code>1</code>， <code>ch[u][x &gt; v[u]]</code>为<code>ch[u][1]</code> 即其左子节点;<br>当<code>x &lt; v[u]</code>, <code>x &gt; v[u]</code> 为 <code>0</code>，  <code>ch[u][x &gt; v[u]]</code>为<code>ch[u][0]</code> 即其右子节点。<br>所以<code>u = ch[u][x &gt; v[u]]</code>就能一直向接近<code>x</code>的位置移动。</li>
</ol>
<h2 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> u = root, fa = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> (u &amp;&amp; x != v[u]) fa = u, u = ch[u][x &gt; v[u]]; <span class="comment">//寻找接近x的位置</span></span><br><span class="line">	<span class="keyword">if</span> (u) cnt[u]++; <span class="comment">// 如果存在， 增加其计数</span></span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		u = ++tot; <span class="comment">// 分配编号</span></span><br><span class="line">		<span class="keyword">if</span> (fa) ch[fa][x &gt; v[fa]] = u; <span class="comment">// 更新父节点的信息</span></span><br><span class="line">		v[u] = x, f[u] = fa, cnt[u] = size[u] = <span class="number">1</span>; <span class="comment">//维护其他信息</span></span><br><span class="line">	&#125;</span><br><span class="line">	splay(u, <span class="number">0</span>); <span class="comment">// 别忘了splay</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="查找前驱"><a href="#查找前驱" class="headerlink" title="查找前驱"></a>查找前驱</h2><p>x的前驱定义为小于x，且最大的数。</p>
<p>先<code>find(x)</code>， x就成为根节点， 根据BST的性质， 比根节点小的数都在根节点的左子树里。 所以小于根节点，且最大的数就是根节点左子树的最大数。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">int pre(int x) &#123;</span><br><span class="line">	find(x); &#x2F;&#x2F; x旋转到根节点</span><br><span class="line">	if (x &gt; v[root]) return root; &#x2F;&#x2F; 判断不存在的情况</span><br><span class="line">	int u &#x3D; ch[root][0]; &#x2F;&#x2F; 找到其左子树</span><br><span class="line">	if (!u) return -1; </span><br><span class="line">	while (ch[u][1]) u &#x3D; ch[u][1]; &#x2F;&#x2F; 不断找最大的</span><br><span class="line">	return u;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="查找后继"><a href="#查找后继" class="headerlink" title="查找后继"></a>查找后继</h2><p>操作和求前驱类似</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">nxt</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	find(x);</span><br><span class="line">	<span class="keyword">if</span> (x &lt; v[root]) <span class="keyword">return</span> root;</span><br><span class="line">	<span class="keyword">int</span> u = ch[root][<span class="number">1</span>];</span><br><span class="line">	<span class="keyword">if</span> (!u) <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">while</span> (ch[u][<span class="number">0</span>]) u = ch[u][<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">return</span> u;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h2><p>删除x时， 把x的前驱旋转到根节点， 后继旋转到根节点的右子节点， 因为x大于其前驱，所以x在根节点的右子树；而x小于其后继， 所以x是根节点的右子树的左子节点。</p>
<p>注意根节点的右子树的左子树有且只有x, 因为只有x大于x的前驱且小于x的后继。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">void del(int x) &#123;</span><br><span class="line">	int px &#x3D; pre(x), nx &#x3D; nxt(x); &#x2F;&#x2F;求前驱后继</span><br><span class="line">	splay(px, 0), splay(nx, root); &#x2F;&#x2F; 把x的前驱旋转到根节点， 后继旋转到根节点的右子节点</span><br><span class="line">	int u &#x3D; ch[nx][0];</span><br><span class="line">	if (cnt[u] &gt; 1) cnt[u]--, splay(u, 0); &#x2F;&#x2F; 如果有多个， 减去并splay</span><br><span class="line">	else ch[nx][0] &#x3D; 0; &#x2F;&#x2F;直接删除</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="查找第k大"><a href="#查找第k大" class="headerlink" title="查找第k大"></a>查找第k大</h2><p>根据之前维护的<code>size</code>查询第k大</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findk</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> u = root;</span><br><span class="line">	<span class="keyword">if</span> (size[u] &lt; x) <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">while</span> (<span class="number">1</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span> (x &lt;= size[ch[u][<span class="number">0</span>]]) u = ch[u][<span class="number">0</span>]; <span class="comment">// 右子树大小大于查询排名， 向右子树查询</span></span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (x &gt; size[ch[u][<span class="number">0</span>]] + cnt[u]) x -= size[ch[u][<span class="number">0</span>]] + cnt[u], u = ch[u][<span class="number">1</span>]; <span class="comment">// 右子树大小+本身大小小于查询排名， 向减一下</span></span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">return</span> u; <span class="comment">// 否则就查到了， return即可</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="查询x的排名"><a href="#查询x的排名" class="headerlink" title="查询x的排名"></a>查询x的排名</h2><p>把查询节点旋转到根节点， 返回左子树的<code>size</code>即可， 注意左子树还有一个多余的负无穷， 所以不用减一。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">rank</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	find(x);</span><br><span class="line">	<span class="keyword">return</span> size[ch[root][<span class="number">0</span>]];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="例题"><a href="#例题" class="headerlink" title="例题"></a>例题</h1><p><a href="https://www.luogu.com.cn/problem/P3369" target="_blank" rel="noopener">洛谷 P3369 普通平衡树</a></p>
<p>参考代码</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXN 100005</span></span><br><span class="line"><span class="keyword">int</span> ch[MAXN][<span class="number">2</span>], cnt[MAXN], size[MAXN], v[MAXN], f[MAXN], root, tot;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123; size[x] = size[ch[x][<span class="number">0</span>]] + size[ch[x][<span class="number">1</span>]] + cnt[x]; &#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">rotate</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> y = f[x], z = f[y], k = (ch[y][<span class="number">1</span>] == x);</span><br><span class="line">	ch[z][ch[z][<span class="number">1</span>] == y] = x, f[x] = z;</span><br><span class="line">	ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;</span><br><span class="line">	ch[x][!k] = y, f[y] = x;</span><br><span class="line">	update(y), update(x);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">splay</span> <span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> t)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">while</span> (f[x] != t) &#123;</span><br><span class="line">		<span class="keyword">int</span> y = f[x], z = f[y];</span><br><span class="line">		<span class="keyword">if</span> (z != t) (ch[y][<span class="number">0</span>] == x) == (ch[z][<span class="number">0</span>] == y) ? rotate(y) : rotate(x);</span><br><span class="line">		rotate(x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (!t) root = x;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">find</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> u = root;</span><br><span class="line">	<span class="keyword">while</span> (ch[u][x &gt; v[u]] &amp;&amp; x != v[u]) u = ch[u][x &gt; v[u]];</span><br><span class="line">	splay(u, <span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> u = root, fa = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> (u &amp;&amp; x != v[u]) fa = u, u = ch[u][x &gt; v[u]];</span><br><span class="line">	<span class="keyword">if</span> (u) cnt[u]++;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		u = ++tot;</span><br><span class="line">		<span class="keyword">if</span> (fa) ch[fa][x &gt; v[fa]] = u;</span><br><span class="line">		v[u] = x, f[u] = fa, cnt[u] = size[u] = <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	splay(u, <span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">pre</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	find(x);</span><br><span class="line">	<span class="keyword">if</span> (x &gt; v[root]) <span class="keyword">return</span> root;</span><br><span class="line">	<span class="keyword">int</span> u = ch[root][<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">if</span> (!u) <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">while</span> (ch[u][<span class="number">1</span>]) u = ch[u][<span class="number">1</span>];</span><br><span class="line">	<span class="keyword">return</span> u;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">nxt</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	find(x);</span><br><span class="line">	<span class="keyword">if</span> (x &lt; v[root]) <span class="keyword">return</span> root;</span><br><span class="line">	<span class="keyword">int</span> u = ch[root][<span class="number">1</span>];</span><br><span class="line">	<span class="keyword">if</span> (!u) <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">while</span> (ch[u][<span class="number">0</span>]) u = ch[u][<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">return</span> u;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">del</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> xp = pre(x), xn = nxt(x);</span><br><span class="line">	splay(xp, <span class="number">0</span>), splay(xn, root);</span><br><span class="line">	<span class="keyword">int</span> u = ch[xn][<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">if</span> (cnt[u] &gt; <span class="number">1</span>) cnt[u]--, splay(u, <span class="number">0</span>);</span><br><span class="line">	<span class="keyword">else</span> ch[xn][<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findk</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> u = root;</span><br><span class="line">	<span class="keyword">if</span> (size[u] &lt; x) <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">while</span> (<span class="number">1</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span> (x &lt;= size[ch[u][<span class="number">0</span>]]) u = ch[u][<span class="number">0</span>];</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (x &gt; size[ch[u][<span class="number">0</span>]] + cnt[u]) x -= size[ch[u][<span class="number">0</span>]] + cnt[u], u = ch[u][<span class="number">1</span>];</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">return</span> u;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">rank</span> <span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	find(x);</span><br><span class="line">	<span class="keyword">return</span> size[ch[root][<span class="number">0</span>]];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span> <span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n, op, x;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</span><br><span class="line">	insert(<span class="number">-10000005</span>), insert(<span class="number">10000005</span>); <span class="comment">//插入正无穷和负无穷</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;op, &amp;x);</span><br><span class="line">		<span class="keyword">if</span> (op == <span class="number">1</span>) insert(x);</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (op == <span class="number">2</span>) del(x);</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (op == <span class="number">3</span>) <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, rank(x));</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (op == <span class="number">4</span>) <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, v[findk(x + <span class="number">1</span>)]); <span class="comment">// 别忘了还有一个负无穷占位， 排名要+1</span></span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (op == <span class="number">5</span>) <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, v[pre(x)]);</span><br><span class="line">		<span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, v[nxt(x)]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

          
            <div class='article_footer'>
              
                
  
    
    



  

  
    
    



  

  
    
    

<section class="widget copyright  desktop mobile">
  <div class='content'>
    
      <blockquote>
        
          
            <p>博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</p>

          
        
          
            <p>本文永久链接是：<a href=https://youxam.gitee.io/2020/07/12/splay/>https://youxam.gitee.io/2020/07/12/splay/</a></p>
          
        
      </blockquote>
    
  </div>
</section>

  

  
    
    

<section class="widget qrcode  desktop mobile">
  

  <div class='content article-entry'>
    
      
        <div class='fancybox'><img src='https://cdn.jsdelivr.net/gh/xaoxuu/cdn-assets/qrcode/wiki_volantis.png'
        
          height='64px'
        ></div>
      
    
      
        <div class='fancybox'><img src='https://cdn.jsdelivr.net/gh/xaoxuu/cdn-assets/qrcode/wiki_volantis.png'
        
          height='64px'
        ></div>
      
    
  </div>
</section>

  


              
            </div>
          
        </div>
        
          


  <section class='meta' id="footer-meta">
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date" itemprop="dateUpdated" datetime="2020-07-12T16:48:49+08:00">
  <a class='notlink'>
    <i class="fas fa-edit fa-fw" aria-hidden="true"></i>
    <p>更新于：Jul 12, 2020</p>
  </a>
</div>

        
      
        
          

        
      
        
          

        
      
        
          
  <div class="new-meta-item share -mob-share-list">
  <div class="-mob-share-list share-body">
    
      
        <a class="-mob-share-qq" title="" rel="external nofollow noopener noreferrer"
          
          href="http://connect.qq.com/widget/shareqq/index.html?url=https://youxam.gitee.io/2020/07/12/splay/&title=splay - Zlii&summary=介绍平衡树的一种—Splay"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-assets/logo/128/qq.png">
          
        </a>
      
    
      
        <a class="-mob-share-qzone" title="" rel="external nofollow noopener noreferrer"
          
          href="https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?url=https://youxam.gitee.io/2020/07/12/splay/&title=splay - Zlii&summary=介绍平衡树的一种—Splay"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-assets/logo/128/qzone.png">
          
        </a>
      
    
      
        <a class="-mob-share-weibo" title="" rel="external nofollow noopener noreferrer"
          
          href="http://service.weibo.com/share/share.php?url=https://youxam.gitee.io/2020/07/12/splay/&title=splay - Zlii&summary=介绍平衡树的一种—Splay"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-assets/logo/128/weibo.png">
          
        </a>
      
    
  </div>
</div>



        
      
    </div>
  </section>


        
        
      </section>
    </article>
  

  
    
  <article class="post white-box reveal comments shadow">
    <section class="article typo">
      <p ct><i class='fas fa-comments'></i> 评论</p>
      
      <section id="comments">
        <div id="valine_container" class="valine_thread">
  <i class="fas fa-cog fa-spin fa-fw fa-2x"></i>
</div>

      </section>
    </section>
  </article>


  




<!-- 根据页面mathjax变量决定是否加载MathJax数学公式js -->


</div>
<aside class='l_side'>
  
  

  
    
    



  <section class="widget toc-wrapper shadow desktop mobile" id="toc-div" >
    
  <header>
    
      <i class="fas fa-list fa-fw" aria-hidden="true"></i><span class='name'>本文目录</span>
    
  </header>


    <div class='content'>
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#BST-二叉排序树"><span class="toc-text">BST(二叉排序树)</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#平衡树"><span class="toc-text">平衡树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Splay-伸展树"><span class="toc-text">Splay(伸展树)</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#本文代码变量含义"><span class="toc-text">本文代码变量含义</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#更新"><span class="toc-text">更新</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#单旋"><span class="toc-text">单旋</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Splay-伸展"><span class="toc-text">Splay(伸展)</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#查找"><span class="toc-text">查找</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#插入"><span class="toc-text">插入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#查找前驱"><span class="toc-text">查找前驱</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#查找后继"><span class="toc-text">查找后继</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#删除"><span class="toc-text">删除</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#查找第k大"><span class="toc-text">查找第k大</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#查询x的排名"><span class="toc-text">查询x的排名</span></a></li></ol>
    </div>
  </section>


  


</aside>



    </div>
    
  
  <footer class="clearfix">
    <br><br>
    
      
        <br>
        <div class="social-wrapper">
          
            
              <a href="mailto:zhang.haoling@outlook.com"
                class="social fas fa-envelope flat-btn"
                target="_blank"
                rel="external nofollow noopener noreferrer">
              </a>
            
          
            
              <a href="https://github.com/youxam"
                class="social fab fa-github flat-btn"
                target="_blank"
                rel="external nofollow noopener noreferrer">
              </a>
            
          
        </div>
      
    
      
        <div><p>Blog content follows the <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en" target="_blank" rel="noopener">Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License</a></p>
</div>
      
    
  </footer>


    <a class="s-top fas fa-arrow-up fa-fw" href='javascript:void(0)'></a>
  </div>
  <div>
    
<script src="https://cdn.jsdelivr.net/npm/jquery@3.4/dist/jquery.min.js"></script>



  <script>
    
    var SEARCH_SERVICE = "hexo" || "hexo";
    var ROOT = "/" || "/";
    if (!ROOT.endsWith('/')) ROOT += '/';
  </script>





  <script async src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-volantis@2/js/instant_page.js" type="module" defer integrity="sha384-OeDn4XE77tdHo8pGtE1apMPmAipjoxUQ++eeJa6EtJCfHlvijigWiJpD7VDPWXV1"></script>



  
  
  
    
<script src="https://cdn.jsdelivr.net/npm/jquery-backstretch@2.1.18/jquery.backstretch.min.js"></script>

    <script type="text/javascript">
      $(function(){
        var imgs=["https://cdn.jsdelivr.net/gh/youxam/pic/miku.png"];
        if ('true' == 'true') {
          function shuffle(arr){
            /*From countercurrent-time*/
            var n = arr.length;
            while(n--) {
              var index = Math.floor(Math.random() * n);
              var temp = arr[index];
              arr[index] = arr[n];
              arr[n] = temp;
            }
          }
          shuffle(imgs);
        }
        if ('.cover') {
          $('.cover').backstretch(
            imgs,
          {
            duration: "20000",
            fade: "1500"
          });
        } else {
          $.backstretch(
            imgs,
          {
            duration: "20000",
            fade: "1500"
          });
        }
      });
    </script>
  



  
    
<script src="https://cdn.jsdelivr.net/npm/aplayer@1.10/dist/APlayer.min.js"></script>

  
    
<script src="https://cdn.jsdelivr.net/npm/meting@2.0/dist/Meting.min.js"></script>

  


<!-- 评论 （PS：只对 valine 做了 Pjax 兼容） -->

  
  
<script src="/js/valine.js"></script>


<script>
  var GUEST_INFO = ['nick', 'mail', 'link'];
  var meta = 'nick,mail,link'.split(',').filter(function (item) {
    return GUEST_INFO.indexOf(item) > -1
  });
  var REQUIRED_FIELDS = ['nick', 'mail', 'link'];
  var requiredFields = 'nick,mail'.split(',').filter(function (item) {
    return REQUIRED_FIELDS.indexOf(item) > -1
  });

  function emoji(path, idx, ext) {
    return path + "/" + path + "-" + idx + "." + ext;
  }

  var emojiMaps = {};
  for (var i = 1; i <= 54; i++) {
    emojiMaps['tieba-' + i] = emoji('tieba', i, 'png');
  }
  for (var i = 1; i <= 101; i++) {
    emojiMaps['qq-' + i] = emoji('qq', i, 'gif');
  }
  for (var i = 1; i <= 116; i++) {
    emojiMaps['aru-' + i] = emoji('aru', i, 'gif');
  }
  for (var i = 1; i <= 125; i++) {
    emojiMaps['twemoji-' + i] = emoji('twemoji', i, 'png');
  }
  for (var i = 1; i <= 4; i++) {
    emojiMaps['weibo-' + i] = emoji('weibo', i, 'png');
  }

  function pjax_valine() {
    var valinePath = $.trim($('#valine-path').text()) === "none" ?
            window.location.pathname : $.trim($('#valine-path').text());

    var valinePlaceholder = $.trim($('#valine-placeholder').text()) === "none" ?
            "快来评论吧~" : $.trim($('#valine-placeholder').text());

    var ALLPATH = '';
    if(ALLPATH != '') valinePath = ALLPATH;

    var valine = new Valine();
    valine.init({
      el: '#valine_container',
      meta: meta,
      placeholder: valinePlaceholder,
      path: valinePath,
      appId: "NHHBL6v9KcAM68Mz3yois8WX-gzGzoHsz",
      appKey: "jbRYugX56wExwSj33dNKJho1",
      pageSize: '10',
      avatar: 'robohash',
      lang: 'zh-cn',
      visitor: 'true',
      highlight: 'true',
      mathJax: 'true',
      enableQQ: 'true',
      requiredFields: requiredFields,
      emojiCDN: 'https://cdn.jsdelivr.net/gh/xaoxuu/cdn-assets/emoji/valine/',
      emojiMaps: emojiMaps
    })
  }

  $(function () {
    pjax_valine();
  });
</script>




<!-- darkmodejs -->



<!-- 复制 -->

  <script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
    function wait(callback, seconds) {
        var timelag = null;
        timelag = window.setTimeout(callback, seconds)
    }

    function pjax_initCopyCode() {
        var copyHtml = '';
        copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
        copyHtml += '<i class="fas fa-copy"></i><span>COPY</span>';
        copyHtml += '</button>';
        $(".highlight .code pre").before(copyHtml);
        $(".article pre code").before(copyHtml);
        var clipboard = new ClipboardJS('.btn-copy', {
            target: function (trigger) {
                return trigger.nextElementSibling
            }
        });
        clipboard.on('success', function (e) {
            let $btn = $(e.trigger);
            $btn.addClass('copied');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-check-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPIED';
            wait(function () {
                $icon.removeClass('fa-check-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        });
        clipboard.on('error', function (e) {
            e.clearSelection();
            let $btn = $(e.trigger);
            $btn.addClass('copy-failed');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-times-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPY FAILED';
            wait(function () {
                $icon.removeClass('fa-times-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        })
    }
    $(function () {
        pjax_initCopyCode()
    });
</script>


<!-- scrollreveal -->

  <script src="https://cdn.jsdelivr.net/npm/scrollreveal@4.0.6/dist/scrollreveal.min.js"></script>
  <script type="text/javascript">
    function pjax_scrollrebeal() {
      ScrollReveal().reveal('.l_main .reveal', {
        distance: '32px',
        duration: '800',
        interval: '20',
        scale: '1',
        easing: 'ease-out'
      });
    }

    $(function () {
      pjax_scrollrebeal();
    });
  </script>

<!-- ******************************** -->

<!-- fancybox -->
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>
<script>
  function pjax_fancybox() {
    $(".article-entry").find("img").not('.inline').not('a img').each(function () { //渲染 fancybox
      var element = document.createElement("a"); // a 标签
      $(element).attr("pjax-fancybox", "");  // 过滤 pjax
      $(element).attr("href", $(this).attr("src"));
      if ($(this).attr("data-original")) {
        $(element).attr("href", $(this).attr("data-original"));
      }
      $(element).attr("data-fancybox", "images");
      var caption = "";   // 描述信息
      if ($(this).attr('alt')) {  // 判断当前页面是否存在描述信息
        $(element).attr('data-caption', $(this).attr('alt'));
        caption = $(this).attr('alt');
      }
      var div = document.createElement("div");
      $(div).addClass("fancybox");
      $(this).wrap(div); // 最外层套 div ，其实主要作用还是 class 样式
      var span = document.createElement("span");
      $(span).addClass("image-caption");
      $(span).text(caption); // 加描述
      $(this).after(span);  // 再套一层描述
      $(this).wrap(element);  // 最后套 a 标签
    })
    $(".article-entry").find("img").fancybox({
      selector: '[data-fancybox="images"]',
      hash: false,
      loop: false,
      closeClick: true,
      helpers: {
        overlay: {closeClick: true}
      },
      buttons: [
        "zoom",
        "close"
      ]
    });
  };
  $(function () {
    pjax_fancybox();
  });
</script>

<!-- ******************************** -->


  
<script src="/js/app.js"></script>




  
    
<script src="/js/search.js"></script>

  



  <script defer src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-busuanzi@2.3/js/busuanzi.pure.mini.js" data-pjax></script>



  
<script src="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.js"></script>

  <script type="text/javascript">
    $(function () {
      Waves.attach('.flat-btn', ['waves-button']);
      Waves.attach('.float-btn', ['waves-button', 'waves-float']);
      Waves.attach('.float-btn-light', ['waves-button', 'waves-float', 'waves-light']);
      Waves.attach('.flat-box', ['waves-block']);
      Waves.attach('.float-box', ['waves-block', 'waves-float']);
      Waves.attach('.waves-image');
      Waves.init();
    });
  </script>



  
<script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-volantis@2/js/comment_typing.js"></script>







    
      


<script src="https://cdn.jsdelivr.net/npm/pjax@0.2.8/pjax.min.js"></script>

<!-- 样式位于：source/css/_third-party/pjaxanimate.styl -->

<div class="pjax-animate">
  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.css">
    <script src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>
    <div id="loading-bar-wrapper"><script>NProgress.configure({parent:"#loading-bar-wrapper",trickleSpeed: 100})</script></div>
    <script>
      window.ShowLoading = function() {
        NProgress.start();
      };
      window.HideLoading = function() {
        NProgress.done();
      }
    </script>
  
</div>

<script>
    var pjax;
    document.addEventListener('DOMContentLoaded', function () {
      pjax = new Pjax({
        elements: 'a[href]:not([href^="#"]):not([href="javascript:void(0)"]):not([pjax-fancybox])',
        selectors: [
          "title",
          "#pjax-container"
        ],
        cacheBust: false,   // url 地址追加时间戳，用以避免浏览器缓存
        timeout: 5000
      });
    });
  
    document.addEventListener('pjax:send', function (e) {
      window.stop(); // 相当于点击了浏览器的停止按钮
      var currentUrl = window.location.pathname;
      var targetUrl = e.triggerElement.href;
      var banUrl = [""];
      if (banUrl[0] != "") {
        banUrl.forEach(item => {
          if(currentUrl.indexOf(item) != -1 || targetUrl.indexOf(item) != -1) {
            window.location.href = targetUrl;
          }
        });
      }
      window.subData = null; // 移除标题（用于一二级导航栏切换处）
      $.fancybox.close();    // 关闭弹窗
      $('.nav-main').find('.list-v').not('.menu-phone').css("display","none"); // 移除小尾巴
      $('.menu-phone.list-v').css("display","none"); // 移除小尾巴
      $('.l_header .switcher .s-search').removeClass('active'); // 关闭移动端激活的搜索框
      $('.l_header').removeClass('z_search-open'); // 关闭移动端激活的搜索框
      $('.wrapper').removeClass('sub'); // 跳转页面时关闭二级导航
      $(window).unbind('resize');    // 解绑
      $(window).unbind('scroll');    // 解绑
      $(window).unbind('click');     // 解绑
      $(document).unbind('scroll');  // 解绑
      window.ShowLoading();
    });
  
    document.addEventListener('pjax:complete', function () {
      // 关于百度统计对 SPA 页面的处理：
      // 方案一：百度统计>管理>单页应用设置中，打开开启按钮即可对SPA进行统计。 https://tongji.baidu.com/web/help/article?id=324
      // 方案二：取消注释下列代码。 https://tongji.baidu.com/web/help/article?id=235
      // 
  
      // 关于谷歌统计对 SPA 页面的处理：
      // 当应用以动态方式加载内容并更新地址栏中的网址时，也应该更新通过 gtag.js 存储的网页网址。
      // https://developers.google.cn/analytics/devguides/collection/gtagjs/single-page-applications?hl=zh-cn
      
      
      $('.nav-main').find('.list-v').not('.menu-phone').removeAttr("style",""); // 移除小尾巴的移除
      $('.menu-phone.list-v').removeAttr("style",""); // 移除小尾巴的移除
      $('script[data-pjax], .pjax-reload script').each(function () {
        $(this).parent().append($(this).remove());
      });
  
      try{
        pjax_fancybox();
        
          
          if ('.cover') {
            $('.cover').backstretch("resize");
          } else {
            $.backstretch("resize");
          }
        
        
          pjax_scrollrebeal();
        
        
          pjax_initCopyCode();
        
        
          pjax_valine();
        
        
        
      } catch (e) {
        console.log(e);
      }
      window.HideLoading();
    });
  
    document.addEventListener('pjax:error', function (e) { 
      window.HideLoading(); 
      window.location.href = e.triggerElement.href; 
    }); 
</script>
  
    
  </div>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
</body>
</html>
